import numpy as np
class PP():
    def __init__(self,puzzle,place_number,start = None, end = None):
        self.block = -1
        self.puzzle = puzzle;
        if (puzzle.T-puzzle).any(): 
            print('Warning: Not a symmetrical cost matrix.')
        self.place_range = range(0,place_number)
        self.start = 0 if not start in self.place_range else start
        self.end = (place_number - 1) if not end in self.place_range else end

        self.open_table = [(self.start,0,-1)]  #(place_index, cost, father)
        self.closed_table = []                          #(i, place_index, cost, father)
        
        self.just_closed = 0
        self.cost_list = np.zeros(5,np.int8) - 1

    def pp_step(self,father_index,father_cost):
        for step in self.place_range:
            if (step != father_index):
                child_cost = self.puzzle[father_index,step]
                if (child_cost != self.block):
                    cost = father_cost + child_cost
                    old_cost = self.cost_list[step]
                    if (old_cost>=0 and cost<old_cost) or old_cost<0 :
                        self.cost_list[step] = cost
                        self.open_table.append(
                            (step,cost,self.just_closed))
        self.open_table.sort(key=lambda item: item[1])
    
    def output(self):
        i,place_index,cost,father = self.closed_table.pop(-1)
        output_list = []
        output_list.insert(0,(place_index,cost))
        while (not father == -1):
            i,place_index,cost,f = self.closed_table.pop(-1)
            if (i==father):
                output_list.insert(0,(place_index,cost))
                father = f
        print(f'Solve:{[index for index,_ in output_list]}')
        print(f'Final minimum cost:{self.cost_list[self.end]}')

    def run(self):
        while(len(self.open_table)>0):
            place_index,cost,father = self.open_table.pop(0)
            old_cost = self.cost_list[place_index]
            if cost <= old_cost or old_cost==-1:
                self.closed_table.append(
                    (self.just_closed,place_index,cost,father))
            if place_index==self.end:
                self.output()
                return True
            self.pp_step(place_index,cost)
            self.just_closed+=1                
        print('No valid access.')
        return False


puzzle = np.array(
    [   [ 0, 2, 3,-1,-1],
        [ 2, 0, 4, 3, 6],
        [ 3, 4, 0, 5, 4],
        [-1, 3, 5, 0, 1],
        [-1, 6, 4, 1, 0]],np.int8
)
object_pp = PP(puzzle,5)
object_pp.run()
pass